24. 统计特殊数字

题目内容

已知所有大于 1 的整数都可以被唯一分解成质数的乘积，我们把这组质数称为该整数的质因子。例如：

• 12 = 2 × 2 × 3，12 的质因子为 [2, 3]
• 7 = 1 × 7，7 的质因子为 [7]

现给定一个正整数 n 和一个质数列表 nums（数字严格递增），请统计数字 1 ∼ n 之中，有哪些数字的质因子仅出现在列表 nums 内，返回符合条件的数字数量。

注意：

• 数字 1 无质因子，作为符合条件的数字纳入统计。
• 质数定义：大于 1 的自然数，除了 1 和它自身外不能被其他自然数整除的数。

数据范围：

• 整数 n：1 ≤ n ≤ 10^12
• 列表 nums 长度 m：1 ≤ m ≤ 5

输入描述

输入共两行：

• 第一行：正整数 n，质数列表长度 m
• 第二行：m 个质数，即质数列表 nums（数字严格递增，以空格分隔）

输出描述

输出一个整数，表示 1 ∼ n 中质因子仅出现在列表 nums 内的数字数量。

样例

样例 1

输入

10 2
2 3

输出

7

说明： 输入参数：上限 n = 10，质数个数 m = 2，允许质因子列表 [2, 3]。统计所有 ≤ 10 且质因子仅为 2、3 的正整数：

• 1（无质因子）
• 2 (2)
• 3 (3)
• 4 (2^2)
• 6 (2 × 3)
• 8 (2^3)
• 9 (3^2)

共 7 个，返回结果 7。

样例 2

输入

15 3
2 3 5

输出

11

说明： 输入参数：上限 n = 15，质数个数 m = 3，允许质因子列表 [2, 3, 5]。统计所有 ≤ 15 且质因子仅为 2、3、5 的正整数：

• 1（无质因子）
• 2 (2)
• 3 (3)
• 4 (2^2)
• 5 (5)
• 6 (2 × 3)
• 8 (2^3)
• 9 (3^2)
• 10 (2 × 5)
• 12 (2^2 × 3)
• 15 (3 × 5)

共 11 个，返回结果 11。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (input) => {
    const [n, m] = input.split(' ').map(Number);
    rl.on('line', (input) => {
        const nums = input.split(' ').map(Number);
        const ans = new Set();
        const dfs = (val) => {
            for (let i = 0; i < nums.length; i++) {
                if (val * nums[i] <= n) {
                    ans.add(val * nums[i]);
                    dfs(val * nums[i]);
                }
            }
        };
        dfs(1);
        console.log(ans.size + 1);
    });
});